Since 1800 the most widely-used methods for secret communications have been secret key encryption methods. Messages are encrypted using a secret key known only to the communicating parties. These keys needed to be distributed to all of the communicating parties, and kept strictly secret from all unauthorized third parties.
In the past, keys were distributed mainly by personal contact, by couriers, or by diplomatic pouch. These methods are unsuitable for modern electronic communications. Keys need to be distributed in a fraction of a second for immediate use.
Modern methods of key distribution generally fall into two classes. The first class depends on having a key authority, a key server, or a key repository. This facility generates keys for each message to be sent, and distributes those keys to all of the parties. This method usually requires each user or client to have a unique ID and some secret parameters which are stored by the key authority. The server generates message keys based on the IDs and secret parameters of the various parties, and sends the message keys to the parties encrypted with their secret keys. So this class of key distribution requires some infrastructure, and some secret keys already distributed to the communicating parties. There also have to be protocols for adding new parties to the network, which might involve physically delivering a key to a new party in the form of a key chip, a disk or a flash drive.
The second method, which is sometimes called key synchronization, requires each communicating party to have a unique ID and some secret data associated with that ID. Either each party must have a table associating all of the user IDs with their corresponding secret data, or there must be repository on the network from which each party can get this secret information. The IDs may be public knowledge, and may be communicated openly, but the secret data must never be divulged. A key for each message between two parties is constructed from their secret data and some additional data unique to that message, such as a message sequence number, or simply the date and time when it is sent. All of this must be set up in advance before any messages can be sent. Each party uses this information to calculate the message key.
Basically, in the first class the key authority generates the message keys and distributes them, but in the second class each party computes the keys in such a way that all parties arrive at the same key. In both classes each user must be supplied beforehand with secret keys and/or secret parameters used to generate keys. There is no way that two parties can establish secure communications without this prior arrangement.
Some patents which describe or utilize these methods are U.S. Pat. Nos. 4,200,700, 5,159,632, 5,271,061, 5,987,130, 6,052,466, 6,212,279, 6,289,105, 6,307,936, 6,363,154, 6,377,689, 6,785,813, 6,987,855, 6,993,136, 7,020,282, 7,065,210, 7,073,066, 7,080,255, 7,096,356, 7,107,246, 7,111,322, 7,120,696, 7,149,308, 7,156,299, 7,167,565, 7,181,014, 7,181,015, 7,263,619, and 7,245,722.
Until recently there was no method for two parties to establish secret communications without prior distribution of secret keys or other secret data if all of their transmissions were being monitored. The great breakthrough in this field is disclosed in U.S. Pat. No. 4,200,770 to Hellman-Diffie-Merkle. In this invention two parties A and B, agree on a large prime number p and a number x in the range 2 to p−2. The two parties independently choose random exponents a and b in the range 2 to p−2. The two parties then raise the base x to the powers a and b modulo p. A sends xa(mod p) to B, and B sends xb(mod p) to A. The two parties then raise the numbers they receive to their own powers. That is, A raises xb(mod p) to the a power, to get xba(mod p), while B raises xa(mod p) to the b power to get xab(mod p). Since xba=xab both parties end up with the same final result, namely xab(mod p) which is then used to produce the cryptographic key for encrypting and decrypting the message.
This allows secure cryptographic keys to be generated on the fly, without any prior distribution of secret keys between the parties. The method is secure because it is computationally difficult to calculate a when p, x and xa(mod p) are given.
The main drawback of the Hellman-Diffie-Merkle key exchange is that it is slow. In order to make the key exchange secure the prime p must be chosen to be very large, at least 100 decimal digits, and preferably more than 200 decimal digits. This makes calculating the quantities xa(mod p), xb(mod p) and xab(mod p) very time-consuming.
The underlying reason why Hellman-Diffie-Merkle key exchange is secure is that exponentiation modulo p is a one-way function. In general, a one-way function f(x,y) is a function where it is easy to compute f(x,y) given the inputs x and y, but difficult or impossible to compute the values of x and y given f(x,y), or where it is difficult or impossible to compute the value of y given x and f(x,y). The best-known example is that it is easy to compute the product pq of two large primes p and q, but given pq it is difficult to factor it into the primes p and q.
Another example of a one-way function is multiplying a vector V by a square matrix M to produce a vector W=MV. Given V and W it is impossible to determine the matrix M. If M is an n×n square matrix and V is an n×1 column vector, then W will also be an n×1 column vector. It is impossible to determine M from V and W because the n2 elements of M are n2 unknown quantities, but MV=W gives only n linear equations in n2 unknowns. For n>1 it is not possible to determine n2 unknowns from only n linear equations. To be clear, it is not merely difficult, as in the case of factoring large numbers, it is impossible.
The essence of the invention herein disclosed, then, is to use the fast operation of matrix multiplication in place of the slow operation of raising a number to a large power modulo a large prime. This will provide a method of key exchange which is both fast and secure. Two variations will be presented, which may be called the one-sided method and the two-sided method.
To lay the foundation for the disclosure and analysis of the invention, it is helpful to review some computer and mathematics basics which underlie the invention. In most modern computers, data, such as letters and numbers, are represented as binary numbers, that is, numbers in the base 2. Each binary digit, or bit, in a binary number may take either the value 0 or the value 1. A group of 8 bits, called a byte, is commonly used to represent small numbers or letters. For example, the byte 01000001 represents the number 65, or the letter “A” in ASCII code.
The ordinary operations of addition, subtraction, multiplication and division can be performed on binary numbers. There are also bitwise logical operations, also called Boolean operations, that can be performed on binary numbers, namely bitwise “and”, bitwise “or” and bitwise “exclusive-or” or “xor”. These operations are performed separately for each corresponding bit position. For example:
ANDORXOR000011110000111100001111010101010101010101010101000001010101111101011010In a byte the leftmost bit is called the high-order bit and has the numeric value 27 or 128, while the rightmost bit is called the low-order bit, or least-significant bit, and has the numeric value 20 or 1.
In terms of the underlying mathematics, if m and n are positive integers, then the residue of n modulo m means the remainder when n is divided by m. The residue of n modulo m is denoted n (mod m) and m is called the modulus. So 42 (mod 10)=2. If x and y have the same residue modulo m this is denoted x=y (mod m). For example, 32=42 (mod 10). Any number which evenly divides m is called a factor of m. If n is a factor of m then m=0 (mod n), for example 12=0 (mod 4). If a positive integer p has no factors except 1 and p itself, then p is called a prime number, or simply a prime. For example, 2, 3, 5, 7 and 11 are primes, but 9 is not prime because it is evenly divisible by 3. If m and n have no factors in common then they are called relatively prime. For example, 8 and 15 are relatively prime.
A matrix is a rectangular array of elements, also called entries. In the simplest case the elements, or scalars, will be numbers. In more advanced treatments of matrices the scalars are elements of a mathematical entity called a ring, and the matrix is said to be over the ring. For present purposes it is sufficient to note that there are two operations on the elements of a ring, commonly called scalar addition and scalar multiplication. Scalar addition, or simply addition, is usually denoted x+y, and scalar multiplication, or simply multiplication, is denoted xy. Scalar addition in a ring is commutative, that is x+y=y+x. If the scalar multiplication is commutative, that is, if xy=yx for all x and y, then the ring is called commutative.
Each ring element has an additive inverse. If every element in the ring, except 0, has a multiplicative inverse, then the ring is called a field. The additive inverse of the scalar x is denoted −x and addition of the additive inverse a+(−x) is normally shortened to a−x, with x−x=0. The multiplicative inverse, when it exists, is denoted x′, with xx′=x′x=1. The multiplication operation in a ring is distributive over addition, which means that x(a+b)=xa+xb and (a+b)x=ax+bx for all a, b and x.
A well-known example of a ring is the integers using standard addition and multiplication. Every integer n has an additive inverse −n, but only the integers 1 and −1 have multiplicative inverses. A well-known example of a field is the rational numbers a/b, where a and b are integers and b≠0. The additive inverse of the rational number a/b is −a/b, and exists for all rational numbers. The multiplicative inverse (a/b)′ of the rational number a/b is b/a and exists for every rational number except 0.
Another example of a ring is the integers modulo some number m. The additive inverse of x modulo m is m−x (mod m). Every integer n which is relatively prime to m will have a multiplicative inverse n′ such that nn′=1 (mod m). In particular, if m is of the form 2u then n will have a multiplicative inverse when it is odd.
A matrix A with m rows and n columns is called a matrix of size m×n, or order m×n, or simply an m×n matrix. The element in the i-th row and j-th column is designated Aij where i can range from 1 to m, and j can range from 1 to n. A matrix with only 1 row is called a row matrix, a matrix with only 1 column is called a column matrix, and a matrix with an equal number of rows and columns is called a square matrix. That is, a row matrix is 1×n, a column matrix is n×1, and a square matrix is n×n.
An m×n matrix A and an n×p matrix B can be multiplied to produce an m×p matrix C. This is denoted AB=C and C is called the matrix product of A and B. The element Cij in the i-th row and j-th column of C is formed from the i-th row of A and the j-th column of B by summing Ai1B1j+Ai2B2j+ . . . +Ain Bnj. The addition and multiplication in this expression is the scalar addition and multiplication in the ring.
Matrix multiplication is associative. That is, if A is an m×n matrix, B is an n×p matrix, and C is a p×r matrix, then (AB)C=A(BC). Consequently, the set of n×n square matrices over a ring is itself a ring.
In a square n×n matrix A an element Aii is called a diagonal element, and the set of elements A11, A22, . . . , Ann is called the diagonal of the matrix. A diagonal matrix is a matrix whose only non-zero elements all lie on the diagonal. The diagonal matrix I whose diagonal elements are all 1 is called the identity matrix. The identity matrix has the property that AI=A and IA=A for any square matrix A.
Matrix multiplication is not commutative. That is, in most cases the matrix product AM will not be the same as MA. In the case AM we say that M is left-multiplied by A, and in the case MA we say that M is right-multiplied by A. If all of the matrices in a set F of matrices commute with each other, then F is called a commutative family of matrices. All of the matrices in a commutative family must be square matrices of the same size. If the ring is commutative, then the n×n diagonal matrices over the ring form a commutative family, but other commutative families, containing non-diagonal matrices, may also exist. It is possible to have a commutative family of matrices over a ring even when the ring itself is not commutative.
If A and B are in the commutative family F, then the product AB commutes with every matrix in F. If C is in F, then (AB)C=A(BC)=A(CB)=(AC)B=(CA)B=C(AB), that is, C commutes with AB. A commutative family F will be called closed if for each pair of matrices A and B in F their product AB is also in F. It will henceforth be assumed that each commutative family of matrices is closed.